#include <iostream>
#include "BinaryTree.h"
using namespace std;

    // Test program

const int NUMS = 40;
const int GAP = 7;

// 在NUMS范围内输出这颗树的内容值
template <typename Comparable>
void printTree(BinaryTree<Comparable> &t)
{
    if(NUMS <= 40){
        cout << "Begin to print tree...\n";
        t.printTree();
        cout << "Finished the print.\n";
    }
}

int main( )
{
    cout << "Checking... (no error output means success)" << endl;

    {
        cout << "--------test for BinarySearchTree--------" << endl;
        BinarySearchTree<int> BinarySearchT1;
        int i;

        for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            BinarySearchT1.insert( i );

        for( i = 1; i < NUMS; i += 2 )
            BinarySearchT1.remove( i );

        printTree(BinarySearchT1);  // 此处从小到大打印树中存储的值

        if( BinarySearchT1.findMin( ) != 2 || BinarySearchT1.findMax( ) != NUMS - 2 )
            cout << "FindMin or FindMax error!" << endl;

        for( i = 2; i < NUMS; i += 2 )
            if( !BinarySearchT1.contains( i ) )
                cout << "Find error (may not remove the element)!" << endl;

        for( i = 1; i < NUMS; i += 2 )
            if( BinarySearchT1.contains( i ) )
                cout << "Find error (may not insert the element)!" << endl;

        BinarySearchTree<int> BinarySearchT2;
        BinarySearchT2 = BinarySearchT1;    // 测试等号重载, copy ctor等.

        // 检查是否赋值成功 
        for( i = 2; i < NUMS; i += 2 )
            if( !BinarySearchT2.contains( i ) )
                cout << "Find error (may fail to assignment)!" << endl;

        for( i = 1; i < NUMS; i += 2 )
            if( BinarySearchT2.contains( i ) )
                cout << "Find error (may fail to assignment)!" << endl;

        // empty测试
        if(BinarySearchT2.isEmpty())
            cout << "Find error (may fail to assignment)!" << endl;
        BinarySearchT2.makeEmpty();
        if(!BinarySearchT2.isEmpty())
            cout << "Find error (may fail to empty the tree)!" << endl;

    }
   
    {
        cout << "--------test for AvlTree--------" << endl;
        AvlTree<int> AvlT1;
        int i;

        for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            AvlT1.insert( i );

        for( i = 1; i < NUMS; i += 2 )
            AvlT1.remove( i );

        printTree(AvlT1);  // 此处从小到大打印树中存储的值

        if( AvlT1.findMin( ) != 2 || AvlT1.findMax( ) != NUMS - 2 )
            cout << "FindMin or FindMax error!" << endl;

        for( i = 2; i < NUMS; i += 2 )
            if( !AvlT1.contains( i ) )
                cout << "Find error (may not remove the element)!" << endl;

        for( i = 1; i < NUMS; i += 2 )
            if( AvlT1.contains( i ) )
                cout << "Find error (may not insert the element)!" << endl;

        AvlTree<int> AvlT2;
        AvlT2 = AvlT1;    // 测试等号重载, copy ctor等.

        // 检查是否赋值成功 
        for( i = 2; i < NUMS; i+=2 )
            if( !AvlT2.contains( i ) )
                cout << "Find error (may fail to assignment)!" << endl;

        for( i = 1; i < NUMS; i+=2 )
            if( AvlT2.contains( i ) )
                cout << "Find error (may fail to assignment)!" << endl;

        // empty测试
        if(AvlT2.isEmpty())
            cout << "Find error (may fail to assignment)!" << endl;
        AvlT2.makeEmpty();
        if(!AvlT2.isEmpty())
            cout << "Find error (may fail to empty the tree)!" << endl;
    }
 
    {
        cout << "--------test for RedBlackTree--------" << endl;
        const int NEG_INF = -9999;
        RedBlackTree<int> RedBlackT1{ NEG_INF };
        int i;

        RedBlackT1.insert(7);   // 测试自己增加的函数 insert( Comparable && x )
                                // 是否有被调用(被调用时, 命令行给出输出提示)
        for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            RedBlackT1.insert( i );

        printTree(RedBlackT1);  // 此处从小到大打印树中存储的值

        if( RedBlackT1.findMin( ) != 1 || RedBlackT1.findMax( ) != NUMS - 1 )
            cout << "FindMin or FindMax error!" << endl;

        for( i = 1; i < NUMS; ++i )
            if( !RedBlackT1.contains( i ) )
                cout << "Find error (may fail to insert)!" << endl;
        if( RedBlackT1.contains( 0 ) )
            cout << "Oops! Where comes the zero?" << endl;
        // 原代码没有实现 remove 功能, 这里不进行测试. 
        
        RedBlackTree<int> RedBlackT2{ NEG_INF };
        RedBlackT2 = RedBlackT1; // 测试等号重载, copy ctor等.

        for( i = 1; i < NUMS; ++i )
            if( !RedBlackT2.contains( i ) )
                cout << "Find error (may fail to assignment)!" << endl;
        if( RedBlackT2.contains( 0 ) )
            cout << "Oops! Where comes the zero?" << endl;

        // empty测试
        if(RedBlackT2.isEmpty())
            cout << "Find error (may fail to assignment)!" << endl;
        RedBlackT2.makeEmpty();
        if(!RedBlackT2.isEmpty())
            cout << "Find error (may fail to empty the tree)!" << endl;
    }

    {
        cout << "--------test for SplayTree--------" << endl;
        SplayTree<int> SplayT1;
        int i;

        SplayT1.insert(7);  // 测试自己增加的函数 insert( Comparable && x )
                            // 是否有被调用(被调用时, 命令行给出输出提示)
        for( i = GAP; i != 0; i = ( i + GAP ) % NUMS )
            SplayT1.insert( i );

        for( i = 1; i < NUMS; i += 2 )
            SplayT1.remove( i );

        printTree(SplayT1);  // 此处从小到大打印树中存储的值

        if( SplayT1.findMin( ) != 2 || SplayT1.findMax( ) != NUMS - 2 )
            cout << "FindMin or FindMax error!" << endl;

        for( i = 2; i < NUMS; i += 2 )
            if( !SplayT1.contains( i ) )
                cout << "Find error (may not remove the element)!" << endl;

        for( i = 1; i < NUMS; i += 2 )
            if( SplayT1.contains( i ) )
                cout << "Find error (may not insert the element)!" << endl;

        SplayTree<int> SplayT2;
        SplayT2 = SplayT1;    // 测试等号重载, copy ctor等.

        // 检查是否赋值成功
        for( i = 2; i < NUMS; i += 2 )
            if( !SplayT2.contains( i ) )
                cout << "Find error (may fail to assignment)!" << endl;

        for( i = 1; i < NUMS; i += 2 )
            if( SplayT2.contains( i ) )
                cout << "Find error (may fail to assignment)!" << endl;

        // empty测试
        if(SplayT2.isEmpty())
            cout << "Find error (may fail to assignment)!" << endl;
        SplayT2.makeEmpty();
        if(!SplayT2.isEmpty())
            cout << "Find error (may fail to empty the tree)!" << endl;
    }

    cout << "Finished the testing." << endl;
    return 0;
}
